package cn.njupt.tree;

import cn.njupt.printer.BinaryTreeInfo;

import java.util.LinkedList;
//普通的二叉树
public class BinaryTree<E> implements BinaryTreeInfo {
    /**
     * 二叉树的根节点
     */
    protected Node<E> root;
    /**
     * 二叉树的节点数量
     */
    protected int size;

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }

    /**
     * 定义的二叉树的节点
     * @param <E>
     */
    static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element,Node<E> parent){
            this.element=element;
            this.parent=parent;
        }

        public boolean hasTwoChildren(){
            return left!=null && right!=null;
        }

        public boolean isLeftChild(){
            return parent!=null && parent.left==this;
        }
        public boolean isRightChild(){
            return parent!=null && parent.right==this;
        }

        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            sb.append(this.element);
            if(this.parent!=null){
                sb.append("parent:").append(parent.element);
            }
            if(this.left!=null){
                sb.append("left:").append(left.element);
            }
            if(this.right!=null){
                sb.append("right:").append(right.element);
            }
            return element.toString();
        }
    }

    public int size(){
        return size;
    }

    public Node<E> getRoot(){
        return root;
    }

    /**
     * 得到node的后继节点
     * @param node 传递的当前节点
     * @return
     */
    public Node<E> getSuccessor(Node<E> node){
        if(node==null) return node;
        if(node.right!=null){
            return getLeftNode(node.right);
        }else{
            Node<E> parent=node.parent;
            while(parent!=null && parent.left!=node){
                node=parent;
                parent=node.parent;

            }
            return parent;
        }
    }
    public Node<E> getLeftNode(Node<E> node){
        while (node.left!=null){
            node=node.left;
        }
        return node;
    }

    /**
     * 判断以root为根节点的树是否是完全二叉树
     * @param root
     * @return
     */
    public boolean isCompleteTree(Node<E> root){
        if(root==null)return true;
        LinkedList<Node> queue=new LinkedList<>();
        queue.add(root);

        boolean leaf=false;
        while(!queue.isEmpty()){
            Node<E> cur=queue.removeFirst();
            Node<E> left=cur.left;
            Node<E> right=cur.right;
            if(leaf&&(left!=null || right!=null)
                || (left==null&& right!=null)){
                return false;
            }
            if(left!=null){
                queue.add(left);
            }
            if(right!=null){
                queue.add(right);
            }else{
                leaf=true;
            }
        }
        return true;
    }

    public void clear(){
        size=0;
        root=null;
    }

    public void inOrderTraversal(Node<E> root){
        if(root==null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.println(root.element);
        inOrderTraversal(root.right);
    }

    public Node<E> createNode(E element,Node<E> parent){
        return new Node<E>(element,parent);
    }
}
